package com.leetcode.algorithm.y22.m07;

import com.leetcode.algorithm.common.ListNode;

/**
 * 142. 环形链表 II
 * 
 * 
 * @author jie.deng
 *
 */
public class Question0142Solution01 {
	
	public ListNode detectCycle(ListNode head) {
		// 先判断是否存在环，以及环的大小n
		ListNode fast = head;
		ListNode slow = head;
		int cnt = 0;
		while (fast != null && fast.next != null) {
			slow = slow.next;
			fast = fast.next.next;
			cnt++;
			if (fast == slow) {
				break;
			}
		}
		if (fast == slow && fast != null && fast.next != null) {
			// 存在环，且环的大小是cnt
			// fast先走cnt步，然后一起走，相会的地方即为环的入口
			fast = head;
			slow = head;
			while (cnt > 0) {
				fast = fast.next;
				cnt--;
			}
			while (fast != slow) {
				fast = fast.next;
				slow = slow.next;
			}
			return fast;
		}
		return null;
	}
    
}